﻿using System.Collections.Generic;
using System.Drawing;

namespace ProblemsSet
{
    public class Problem_78 : BaseProblem
    {
        public override object GetResult()
        {
            const int div = 1000000;
            const int mx = 500;

            var kfs = new Point[mx+1];
            kfs[0] = new Point(1, 0);

            for (var i =1; i <= mx/2; i++)
            {
                kfs[2*i - 1] = new Point(i%2==0?1:-1 ,(int)MathLogic.GetPenta(i));
                kfs[2 * i] = new Point(i % 2 == 0 ? 1 : -1, (int)MathLogic.GetPenta(-i));
            }

            var p = new List<string>() {"1", "1", "2"};

            long cur = 3;
            while(true)
            {
                long n = 1;
                var rs = "0";
                while (kfs[n].Y<=cur)
                {
                    if (kfs[n].X < 0)
                    {
                        rs = MathLogic.SummString(rs, p[(int)(cur - kfs[n].Y)]);
                    }
                    else
                    {
                        rs = MathLogic.SubstractString(rs, p[(int)(cur - kfs[n].Y)]);
                    }
                    n++;
                }
                if (rs.EndsWith("000000"))
                    return cur;
                cur++;
                p.Add(rs);

            }


        }

        public override string Problem
        {
            get
            {
                return @"Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.

OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O
Find the least value of n for which p(n) is divisible by one million.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 55374;
            }
        }

    }
}
